<html>
<head>
<style>
	.controls {
		height: 100px;
	}
	
	.chain .link {
		float: left;
		width: 100px;
		height: 100px;
		border: 1px solid black;
		padding: 5px;
		margin: 10px;
		position: relative;
	}
	.chain .link .option {
		color: gray;
		font-size: .9em;
		font-family: Sans Serif;
	}
	
	.output, .options {
		clear: both;
	}
	
	.options {
		padding: 20px;
	}
	
	.options > .opt {
		display: inline-block;
	}
	
	
	._add, ._mul, ._neg, ._term, ._sin, ._cos, ._ovar, ._uvar {
		display: inline-block;
		white-space: nowrap;
		padding: 2px;
	}
	
	._add { border: 2px solid purple; }
	._mul { border: 2px solid green; }
	._neg { border: 2px solid gray; }
	._term { border: 2px solid orange; }
	._sin { border: 2px solid pink; }
	._cos { border: 2px solid pink; }
	._ovar { border: 2px solid black; }
	._uvar { border: 2px solid silver; }


</style>

<script type="text/javascript">
	/*
	chain editing, cursor, delete
	trim unused variables
	code output options
		variable naming scheme
		don't ghost existing user vars
		output var names
	check correct matrix multiply order
	optimize out arbitrary expressions instead of just terms
	deg/rad input option
	fractions of pi
	option to precalculate constant trig fns
	row major/column major code output option
	count and compare number of operations
	
	*/
	
	function $(sel, n) {
		return (n || document).querySelector(sel);
	}
	function $all(sel, n) {
		return (n || document).querySelectorAll(sel);
	}

	function $ev(sel, evs, cb) {
		var a = evs.split(' ');
		for(var ev of a) {
			var ns = document.querySelectorAll(sel);
			for(var n of ns) n.addEventListener(ev, cb);
		}
	}
	function $selectVal(sel, n) {
		var s = (n || document).querySelector(sel);
		return s && s.selectedOptions && s.selectedOptions[0] && s.selectedOptions[0].value || null;
	}
	function $show(sel, n) {
		var a = (n || document).querySelectorAll(sel);
		for(var i = 0; i < a.length; i++) {
			a[i].style.display = 'block';
		}
	}

	function $hide(sel, n) {
		var a = (n || document).querySelectorAll(sel);
		for(var i = 0; i < a.length; i++) {
			a[i].style.display = 'none';
		}
	}
	
	function mkElem(name, classes, contents) {
		var e = document.createElement(name);
		if(classes instanceof Array) {
			e.classes = classes;
		}
		else e.className = classes;
		
		e.innerHTML = contents;
		
		return e;
	}
	
	window.addEventListener('load', function() {
		
		$ev('.controls .transform-type', 'change', function(e) {
			var val = e.target.selectedOptions[0].value;
			
			if(val == '') return;
			
			$hide('.controls .transform-option');
			$show('.controls .'+val+'-options');
		})
		
		
		$ev('.controls button[name="add"]', 'click', function(e) { // todo: debounce
			var transf = $selectVal('.controls .transform-type');
			
			if(transf == '') return; // todo: error message
			
			var options = grabOptions('.controls .'+transf+'-options')
			options.transform = transf;
			
			addTransform(-1, options);
			
			$hide('.controls .transform-option');
			// TODO: reset values
			$('.controls .transform-type').selectedIndex = 0;
		})
		
		addTransform(-1, {transform: 'rotAxis', X: uvar('a'), Y:uvar('b'), Z: uvar('c'), Theta: uvar('d')});
		addTransform(-1, {transform: 'rotAxis', X: uvar('e'), Y:uvar('f'), Z: uvar('g'), Theta: uvar('h')});
		addTransform(-1, {transform: 'scale', X: uvar('i'), Y: uvar('j'), Z: uvar('k')});
		addTransform(-1, {transform: 'rotAxis', X: uvar('p'), Y: uvar('m'), Z: uvar('n'), Theta: uvar('o')});
		
		$ev('.output button[name="clear"]', 'click', function(e) { // todo: debounce
			chain = [];
			$('.chain').innerHTML = '';
			$('.output .results').innerHTML = '';
			$('.output .vars').innerHTML = '';
			$('.output .code').innerHTML = '';
		});
		
		$ev('.output button[name="solve"]', 'click', function(e) { // todo: debounce
			if(chain.length == 0) return;
			var cont = $('.output .results');
			
			var handedness = $('.options input[name="handedness"]:checked').value;
			var vector_output = $('.options input[name="matvec_output"]:checked').value;
			
			var O = {};
			var m = $all('.CAS-options input[type="checkbox"]').forEach(function(x) {
				O[x.name] = !!x.checked;
			});
			
			
			
			var mchain = null; 
			
			for(var c of chain) {
				var e = mkElem('div', 'matrix', '');
				
				var mat = getTransformMatrix(c, handedness);
				
				if(mchain === null) mchain = mat;
				else mchain = mul(mat, mchain);
			}
			
			if(vector_output == 'vector') {
				mchain = mul({op: 'vec', arg1: [uvar('X'), uvar('Y'), uvar('Z'), uvar('W')]}, mchain)
			}
			
// 			cont.innerHTML = printXP(txtPrintFns, mchain);
			
			var context = {
				xp: mchain,
				vardef: {},
				varalloc: {},
				varnum: 1,
			};
			
			if(O.factor_trig) {
				factor_builtins(context);
			}
			
			context.xp = fullyOptimize(context.xp, [multiply_matrices_and_vectors]);
			
			var optFns = [];
			if(O.constant_fold) optFns.push(constant_fold);
			if(O.distribute) optFns.push(distribute_terms);
			optFns.push(combine_terms);
			
			context.xp = fullyOptimize(context.xp, optFns);
			
			if(O.factor_terms) {
				factor_ovars(context);
				factor_ovars(context);
// 				factor_ovars(context);
// 				factor_ovars(context);
				
				factor_terms(context);
				factor_terms(context);
			}
			
			context.xp = fullyOptimize(context.xp, optFns);
	
			$('.output .vars').innerHTML = '';
			for(var k in context.vardef) {
				var d = printXP(debugPrintFns, context.vardef[k]);
// 				d += printXP(debugPrintFns, context.vardef[k][1]);
				$('.vars').appendChild(mkElem('div', '', k + ' = ' + d));
			}
			
// 			context.xp = fullyOptimize(context.xp, [combine_terms]);
			
			cont.innerHTML = printXP(debugPrintFns, context.xp);
			
			
			var codeOpts = {
				lineTerm: ';',
				scalarDecl: 'float',
			};
			
			var decls = '';
			for(var k in context.vardef) {
				decls += codeOpts.scalarDecl + ' ' + k + ' = ' 
					+  printCodeXP(codePrintFns, context.vardef[k]) + codeOpts.lineTerm + '\n';
			}
			
			$('.code').innerHTML = decls + printCodeXP(codePrintFns, context.xp, codeOpts);
			
			
			
		});
	});
	
	function factor_ovars(context) {
		
		var term_pairs = [];
		var terms = {};
		
		walk_ops(context.xp, function(xp) {
			if(xp.op == 'term') {
				for(t1 in xp.arg2) {
					for(var t2 = (t1|0) + 1; t2 < xp.arg2.length; t2++) {
						var p = printXP(txtPrintFns, xp.arg2[t1]);
						var q = printXP(txtPrintFns, xp.arg2[t2]);
						var key = p+':'+q;
						terms[key] = [xp.arg2[t1], xp.arg2[t2]];
						term_pairs.push(key);
					}
				}
			}
			
		});
		
		
		
		
		var counts = {}
		
		term_pairs.map(function(x) {
			counts[x] = (counts[x]|0) + 1;
		});
		
		var acounts = [];
		for(var k in counts) {
			if(counts[k] < 2) continue;
			
			acounts.push([counts[k], k]); 
			var v = 'o'+(context.varnum++);
			context.varalloc[k] = v;
			context.vardef[v] = mul(terms[k]);
		}
		
		var aa = acounts.sort(function(a,b) { return b[0] - a[0] });
		
		[xxx, context.xp] = optimize_op(context.xp, function(op, a1, a2) {
			if(op == 'term') {
				var out_arg2 = [];
			
				for(var t2 = 1; t2 < a2.length; t2++) {
					
					var p = printXP(txtPrintFns, a2[t2 - 1]);
					var q = printXP(txtPrintFns, a2[t2]);
					var key = p+':'+q;
					
					if(!context.varalloc[key]) {
						out_arg2.push(a2[t2 - 1]);
						continue;
					}
					
					out_arg2.push({op: 'ovar', arg1: context.varalloc[key]});
					t2++;
					
// 							terms[key] = [xp.arg2[t1], xp.arg2[t2]];
// 							term_pairs.push(key);
				}
				
				if(t2 <= a2.length) { // BUG: this may be borked
					out_arg2.push(a2[a2.length - 1]);
				}
				
				return {
					op: 'term',
					arg1: a1,
					arg2: out_arg2,
				}
			}
			
			return false;
		});
		
	}
	
	function factor_builtins(context) {
		
		var terms = {};
		
		
		walk_ops(context.xp, function(xp) {
			if(xp.op == 'sin' || xp.op == 'cos') {
				if(!is_const(xp)) return false;
				
				var k = printXP(txtPrintFns, xp);
				terms[k] = xp;
			}
			
		});
		
		for(var k in terms) {
			var v = 'o'+(context.varnum++);
			context.varalloc[k] = v;
			context.vardef[v] = terms[k];
		}
// 		console.log('vd', context.vardef);
		
		[xxx, context.xp] = optimize_op(context.xp, function(op, a1, a2) {
			if(op == 'sin' || op == 'cos') {
				
				var k = printXP(txtPrintFns, {op: op, arg1: a1, arg2: a2});
				var v = context.varalloc[k];
				
				if(!v) return false;
				
				return {
					op: 'ovar',
					arg1: v
				};
			}
			
			return false;
		});
		
	}
	
	// assumes arg1 is an array
	function is_bare(xp) {
		for(var x of xp.arg1) {
			if(is_op(x, 'add') || is_op(x, 'mul')) return false;
		}
		return true;
	}
	
	function factor_terms(context) {
		
		var terms = {};
		var term_pairs = [];
		
		
		walk_ops(context.xp, function(xp) {
			if(xp.op == 'add' || xp.op == 'mul') {
				if(!is_bare(xp)) return false;
				
				for(t1 in xp.arg1) {
					for(var t2 = (t1|0) + 1; t2 < xp.arg1.length; t2++) {
						var p = printXP(txtPrintFns, xp.arg1[t1]);
						var q = printXP(txtPrintFns, xp.arg1[t2]);
						var key = p+':'+q;
						terms[key] = [xp.arg1[t1], xp.arg1[t2]];
						term_pairs.push(key);
					}
				}
			}
			
		});
		
		var counts = {}
		
		term_pairs.map(function(x) {
			counts[x] = (counts[x]|0) + 1;
		});
		
		var acounts = [];
		for(var k in counts) {
			if(counts[k] < 2) continue;
			
			var kk = k.split(':');
			acounts.push([counts[k], k, kk[0], kk[1], terms[k][0], terms[k][1]]); 
			var v = 'ot'+(context.varnum++);
			context.varalloc[k] = v;
			context.vardef[v] = mul(terms[k]);
		}
		
// 		console.log('vd', context.vardef);
		var aa = acounts.sort(function(a,b) { return b[0] - a[0] });
		console.log(aa);
		
		// TODO: this section is horribly inefficient
		[xxx, context.xp] = optimize_op(context.xp, function(op, a1, a2) {
			if(op == 'add' || op == 'mul') {
				if(!is_bare({arg1: a1})) return false;
				
				var out = [];
				
				var xpcounts = {};
				var xpcache = {};
				for(var x of a1) {
					var k = printXP(txtPrintFns, x);
					xpcounts[k] = (xpcache[k]|0) + 1;
					xpcache[k] = x;
				}
				
				// look through the list, looping through the options, taking the best one
				for(var a of aa) {
					if(xpcounts[a[2]] > 0 && xpcounts[a[3]] > 0) {
						var v = context.varalloc[a[1]];
						
						out.push(v);
						xpcounts[a[2]]--;
						xpcounts[a[3]]--;
					}
				}
				
				// push on the remainders
				for(var k in xpcounts) {
					var a = xpcounts[k];
					for(var i = a|0; i > 0; i--) {
						out.push(xpcache[k]);
					}
				}
				
// 				var k = printXP(txtPrintFns, {op: op, arg1: a1, arg2: a2});
// 				var v = context.varalloc[k];
				
// 				if(!v) return false;
				
				return {
					op: 'add',
					arg1: out
				};
			}
			
			return false;
		});
		
	}
	
	
	
	
	// runs a set of optimization functions until they all stabilize
	function fullyOptimize(input, fns) {
		
		var mod;
		for(var i = 0; i < 100; i++) {
			var m = false;
			for(var fn of fns) {
				[mod, input] = optimize_op(input, fn);
				m = m || mod;
			}
			
			if(m) {
				continue;
			}
			else {
// 				console.log("optimization rounds: " + (i + 1));
				break;
			}
		}
		
		return input;
	}
	
	
	function grabOptions(sel) {
		var cont = $all(sel + ' input');
		var o = {};
		
		for(var opt of cont) {
			if(parseFloat(opt.value) == opt.value) {
				o[opt.name] = parseFloat(opt.value);
			}
			else {
				o[opt.name] = uvar(opt.value);
			}
		}
		
		return o;
	}
	
	var chain = [];
	
	function addTransform(index, options) {
		if(index == -1) {
			chain.push(options);
		}
		else {
			chain.splice(index, 0, options);
		}
		renderChain($('.chain'), chain);
	}
	

	
	function renderChain(target, chain) {
		target.innerHTML = '';
		
		for(var c of chain) {
			var d = document.createElement('div');
			d.className = 'link';
			
			var name = document.createElement('div');
			name.className = 'name';
			name.innerHTML = c.transform;
			d.appendChild(name);
			
			if(c.X) {
				d.appendChild(mkElem('div', 'option', '[' + c.X + ', ' + c.Y + ', ' + c.Z + ']'));
			}
			if(c.Theta) {
				d.appendChild(mkElem('div', 'option', 'Theta: ' + c.Theta));
			}
			
			// delete button
// 			d.appendChild()
			
			target.appendChild(d);
		} 
	}
	
	function is_op(xp, op) {
		return (typeof(xp) == 'object' && xp.op == op);
	}
	
	var codePrintFns = {
		num: function(fns, xp, opts) { return xp + ''; },
		ovar: function(fns, xp, opts) { return xp.arg1 + ''; },
		uvar: function(fns, xp, opts) { return xp.arg1 + ''; },
		cos: function(fns, xp, opts) { return 'cos(' + printCodeXP(fns, xp.arg1, opts) + ')'; },
		sin: function(fns, xp, opts) { return 'sin(' + printCodeXP(fns, xp.arg1, opts) + ')'; },
		neg: function(fns, xp, opts) { return '-' + printCodeXP(fns, xp.arg1, opts); },
		mul: function(fns, xp, opts) { 
			
			return '(' + 
				xp.arg1.map(function(x) { return printCodeXP(fns, x, opts); }).join(' * ') +
				')';
		},
		add: function(fns, xp, opts) { 
			
			return '(' + 
				xp.arg1.map(function(x) { return printCodeXP(fns, x, opts); }).join(' + ') +
				')';
		},
		vec: function(fns, xp, opts) {
			var acc = '\n';
			labels = ['X2', 'Y2', 'Z2', 'W2'];
			for(var b = 0; b < 4; b++) {
				acc += opts.scalarDecl + ' ' + labels[b] + ' = '
					+ printCodeXP(fns, xp.arg1[b], opts) + opts.lineTerm + '\n';
			}
			return acc;
		},
		mat: function(fns, xp, opts) {
			var acc = '\n';
			for(var a = 0; a < 4; a++) {
				for(var b = 0; b < 4; b++) {
					acc += 'm[' + a + '][' + b + '] = '
						+ printCodeXP(fns, xp.arg1[a][b], opts) + opts.lineTerm + '\n';
				}
			}
			return acc;
		},
		term: function(fns, xp, opts) {
			var acc = '';
// 			acc += '(';
			
			if(xp.arg1 != 1) {
				if(xp.arg1 == -1) acc += '-';
				else acc += xp.arg1 + ' * ';
			}
			
			acc += xp.arg2.map(function(x) {
				return printCodeXP(fns, x, opts);
			}).join(' * ');
			
// 			acc += ')';
			
			return acc;
		}
	}
	
	
	var txtPrintFns = {
		ovar: function(fns, xp) { return xp.arg1 + ''; },
		uvar: function(fns, xp) { return xp.arg1 + ''; },
		cos: function(fns, xp) { return 'cos(' + printXP(fns, xp.arg1) + ')'; },
		sin: function(fns, xp) { return 'sin(' + printXP(fns, xp.arg1) + ')'; },
		neg: function(fns, xp) { return '-' + printXP(fns, xp.arg1); },
		mul: function(fns, xp) { 
			
			return '' + 
				xp.arg1.map(function(x) { return printXP(fns, x); }).join(' * ') +
				'';
			
			if(is_op(xp.arg1, 'add') && is_op(xp.arg2, 'add')) {
				return printXP(fns, xp.arg1) + printXP(fns, xp.arg2);
			}
			if((is_num(xp.arg1) || is_builtin(xp.arg1)) && is_op(xp.arg2, 'add')) {
				return printXP(fns, xp.arg1) + printXP(fns, xp.arg2);
			}
			if((is_num(xp.arg2) || is_builtin(xp.arg2)) && is_op(xp.arg1, 'add')) {
				return printXP(fns, xp.arg2) + printXP(fns, xp.arg1);
			}
			
			return printXP(fns, xp.arg1) + ' * ' + printXP(fns, xp.arg2); 
		},
		add: function(fns, xp) { 
			
			return '(' + 
				xp.arg1.map(function(x) { return printXP(fns, x); }).join(' + ') +
				')';
			
 			if(is_op(xp.arg2, 'neg')) {
				return '(' + printXP(fns, xp.arg1) + ' - ' + printXP(fns, xp.arg2.arg1) + ')'; 
			}
			else {
				return '(' + printXP(fns, xp.arg1) + ' + ' + printXP(fns, xp.arg2) + ')'; 
			}
		},
		vec: function(fns, xp) {
			var acc = '[';
			for(var b = 0; b < 4; b++) {
				acc += printXP(fns, xp.arg1[b]) + (b < 3 ? ', ' : '');
			}
			acc += ']';
			return acc;
		},
		mat: function(fns, xp) {
			var acc = '[';
			for(var a = 0; a < 4; a++) {
				acc += '[';
				for(var b = 0; b < 4; b++) {
					acc += printXP(fns, xp.arg1[a][b]) + (b < 3 ? ', ' : '');
				}
				acc += ']';
			}
			acc += ']';
			return acc;
		},
		term: function(fns, xp) {
			var acc = '' + (xp.arg1 == 1 ? '' : xp.arg1);
			
			for(var c of xp.arg2) {
				acc += printXP(fns, c);
			}
			acc += '';
			return acc;
		}
	}
	
	var htmlPrintFns = {
		ovar: function(fns, xp) { return '<b>' + xp.arg1 + '</b>'; },
		uvar: function(fns, xp) { return '<b>' + xp.arg1 + '</b>'; },
		cos: function(fns, xp) { return '<i>cos</i>(' + printXP(fns, xp.arg1) + ')'; },
		sin: function(fns, xp) { return '<i>sin</i>(' + printXP(fns, xp.arg1) + ')'; },
		neg: function(fns, xp) { return '-' + printXP(fns, xp.arg1); },
		mul: function(fns, xp) { 
			
			return '' + 
				xp.arg1.map(function(x) { return printXP(fns, x); }).join(' * ') +
				'';
			
			if(is_op(xp.arg1, 'add') && is_op(xp.arg2, 'add')) {
				return printXP(fns, xp.arg1) + printXP(fns, xp.arg2);
			}
			if((is_num(xp.arg1) || is_builtin(xp.arg1)) && is_op(xp.arg2, 'add')) {
				return printXP(fns, xp.arg1) + printXP(fns, xp.arg2);
			}
			if((is_num(xp.arg2) || is_builtin(xp.arg2)) && is_op(xp.arg1, 'add')) {
				return printXP(fns, xp.arg2) + printXP(fns, xp.arg1);
			}
			
			return printXP(fns, xp.arg1) + ' * ' + printXP(fns, xp.arg2); 
		},
		add: function(fns, xp) { 
			
			return '(' + 
				xp.arg1.map(function(x) { return printXP(fns, x); }).join(' + ') +
				')';
			
 			if(is_op(xp.arg2, 'neg')) {
				return '(' + printXP(fns, xp.arg1) + ' - ' + printXP(fns, xp.arg2.arg1) + ')'; 
			}
			else {
				return '(' + printXP(fns, xp.arg1) + ' + ' + printXP(fns, xp.arg2) + ')'; 
			}
		},
		vec: function(fns, xp) {
			var acc = '<table class="matrix">';
			acc += '<tr>';
			for(var b = 0; b < 4; b++) {
				acc += '<td>' + printXP(fns, xp.arg1[b]) + '</td>';
			}
			acc += '</tr>';
			acc += '</table>';
			return acc;
		},
		mat: function(fns, xp) {
			var acc = '<table class="matrix">';
			for(var a = 0; a < 4; a++) {
				acc += '<tr>';
				for(var b = 0; b < 4; b++) {
					acc += '<td>' + printXP(fns, xp.arg1[a][b]) + '</td>';
				}
				acc += '</tr>';
			}
			acc += '</table>';
			return acc;
		},
		term: function(fns, xp) {
			var acc = '' + (xp.arg1 == 1 ? '' : xp.arg1);
			
			for(var c of xp.arg2) {
				acc += printXP(fns, c);
			}
			acc += '';
			return acc;
		}
	}
	
	var debugPrintFns = {
		ovar: function(fns, xp) { return '<span class="_ovar">' + xp.arg1 + '</span>'; },
		uvar: function(fns, xp) { return '<span class="_ovar">' + xp.arg1 + '</span>'; },
		cos: function(fns, xp) { return '<span class="_cos">cos(' + printXP(fns, xp.arg1) + ')</span>'; },
		sin: function(fns, xp) { return '<span class="_sin">sin(' + printXP(fns, xp.arg1) + ')</span>'; },
		neg: function(fns, xp) { return '<span class="_neg">-' + printXP(fns, xp.arg1) + '</span>'; },
		mul: function(fns, xp) { 
			return '<span class="_mul">' + 
				xp.arg1.map(function(x) { return printXP(fns, x); }).join(' * ') +
				'</span>';
		},
		add: function(fns, xp) { 
			return '<span class="_add">(' + 
				xp.arg1.map(function(x) { return printXP(fns, x); }).join(' + ') +
				')</span>';
		},
		vec: function(fns, xp) {
			var acc = '<table class="matrix _matrix">';
			var labels = ["X'", "Y'", "Z'", "W'"];
			for(var b = 0; b < 4; b++) {
				acc += '<tr><td>' + labels[b] + ' = ' + printXP(fns, xp.arg1[b]) + '</td></tr>';
			}
			acc += '</table>';
			return acc;
		},
		mat: function(fns, xp) {
			var acc = '<table class="matrix _matrix">';
			for(var a = 0; a < 4; a++) {
				acc += '<tr>';
				for(var b = 0; b < 4; b++) {
					acc += '<td> ' + printXP(fns, xp.arg1[a][b]) + '</td>';
				}
				acc += '</tr>';
			}
			acc += '</table>';
			return acc;
		},
		term: function(fns, xp) {
			var acc = '<span class="_term">';
			if(xp.arg1 != 1) {
				if(xp.arg1 == -1) acc += '-';
				else acc += xp.arg1;
			}
			for(var c of xp.arg2) {
				acc += printXP(fns, c);
			}
			acc += '</span>';
			return acc;
		}
	}
	
	
	function printXP(fns, xp) {
		if(typeof(xp) == 'object') return fns[xp.op](fns, xp);
		else return xp;
	}
	
	function printCodeXP(fns, xp, opts) {
		if(typeof(xp) == 'object') return fns[xp.op](fns, xp, opts);
		else return fns['num'](fns, xp, opts);
	}
	
	
	function is_negative(xp) {
		if(typeof(xp) == 'object') {
			if(xp.op == 'neg') {
				return !is_negative(xp.arg1);
			}
			
			return false;
		}
		
		var v = parseFloat(v);
		return v < 0;
	}
	
	function identMatrix() {
		return {op: 'mat', arg1: [
			[1, 0, 0, 0],
			[0, 1, 0, 0],
			[0, 0, 1, 0],
			[0, 0, 0, 1],
		]};
	}
	
	function ovar(x) { return {op: 'ovar', arg1: x}; };
	function uvar(x) { return {op: 'uvar', arg1: x}; };
	function cos(x) { return {op: 'cos', arg1: x}; };
	function sin(x) { return {op: 'sin', arg1: x}; };
	function neg(x) { return {op: 'neg', arg1: x}; };
	function mul(x, y) { 
		if(x instanceof Array) return {op: 'mul', arg1: x};
		return {op: 'mul', arg1: [x, y]}; 
	};
	function add(x, y) { 
		if(x instanceof Array) return {op: 'add', arg1: x};
		return {op: 'add', arg1: [x, y]}; 
	};
	function oneminus(x) { 
		return add(1, neg(x));
	};
	function sq(x) { 
		return mul(x, x);
	};
	
	function getTransformMatrix(xfm, handedness) {
		
		if(xfm.transform == 'rotX') {
			if(handedness == 'left') {
				return {op: 'mat', arg1: [
					[1, 0,                   0,              0],
					[0, cos(xfm.Theta),      sin(xfm.Theta), 0],
					[0, neg(sin(xfm.Theta)), cos(xfm.Theta), 0],
					[0, 0,                   0,              1],
				]};
			}
			else {
				return {op: 'mat', arg1: [
					[1, 0,              0,                   0],
					[0, cos(xfm.Theta), neg(sin(xfm.Theta)), 0],
					[0, sin(xfm.Theta),     cos(xfm.Theta),  0],
					[0, 0,              0,                   1],
				]};
			}
		}
		else if(xfm.transform == 'rotY') {
			if(handedness == 'left') {
				return {op: 'mat', arg1: [
					[cos(xfm.Theta), 0, neg(sin(xfm.Theta)), 0],
					[0,              1, 0,                   0],
					[sin(xfm.Theta), 0, cos(xfm.Theta),      0],
					[0,              0, 0,                   1],
				]};
			}
			else {
				return {op: 'mat', arg1: [
					[cos(xfm.Theta),      0, sin(xfm.Theta), 0],
					[0,                   1, 0,              0],
					[neg(sin(xfm.Theta)), 0, cos(xfm.Theta), 0],
					[0,                   0, 0,              1],
				]};
			}
		}
		else if(xfm.transform == 'rotZ') {
			if(handedness == 'left') {
				return {op: 'mat', arg1: [
					[cos(xfm.Theta),      sin(xfm.Theta), 0, 0],
					[neg(sin(xfm.Theta)), cos(xfm.Theta), 0, 0],
					[0,                   0,              1, 0],
					[0,                   0,              0, 1],
				]};
			}
			else {
				return {op: 'mat', arg1: [
					[cos(xfm.Theta), neg(sin(xfm.Theta)), 0, 0],
					[sin(xfm.Theta), cos(xfm.Theta),      0, 0],
					[0,              0,                   1, 0],
					[0,              0,                   0, 1],
				]};
			}
		}
		else if(xfm.transform == 'scale') {
			return {op: 'mat', arg1: [
				[xfm.X, 0,     0,     0],
				[0,     xfm.Y, 0,     0],
				[0,     0,     xfm.Z, 0],
				[0,     0,     0,     1],
			]};
		}
		else if(xfm.transform == 'translate') {
			return {op: 'mat', arg1: [
				[1, 0, 0, xfm.X],
				[0, 1, 0, xfm.Y],
				[0, 0, 1, xfm.Z],
				[0, 0, 0, 1],
			]};
		}
		else if(xfm.transform == 'rotAxis') {
			var c = cos(xfm.Theta);
			var s = sin(xfm.Theta);
			var omc = oneminus(cos(xfm.Theta));
			if(handedness == 'left') {
				return {op: 'mat', arg1: [
					[
						add(mul([omc, xfm.X, xfm.X]), c), 
						add(mul([omc, xfm.X, xfm.Y]), mul(neg(s), xfm.Z)),
						add(mul([omc, xfm.X, xfm.Z]), mul(s, xfm.Y)),
						0
					],
					[
						add(mul([omc, xfm.Y, xfm.X]), mul(s, xfm.Z)), 
						add(mul([omc, xfm.Y, xfm.Y]), c), 
						add(mul([omc, xfm.Y, xfm.Z]), mul(neg(s), xfm.X)), 
						0
					],
					[
						add(mul([omc, xfm.Z, xfm.X]), mul(neg(s), xfm.Y)), 
						add(mul([omc, xfm.Z, xfm.Y]), mul(s, xfm.X)), 
						add(mul([omc, xfm.Z, xfm.Z]), c), 
						0
					],
					[0, 0, 0, 1],
				]};
			}
			else {
				return {op: 'mat', arg1: [
					[
						add(mul([omc, xfm.X, xfm.X]), c), 
						add(mul([omc, xfm.X, xfm.Y]), mul(s, xfm.Z)),
						add(mul([omc, xfm.X, xfm.Z]), mul(neg(s), xfm.Y)),
						0
					],
					[
						add(mul([omc, xfm.Y, xfm.X]), mul(neg(s), xfm.Z)), 
						add(mul([omc, xfm.Y, xfm.Y]), c), 
						add(mul([omc, xfm.Y, xfm.Z]), mul(s, xfm.X)), 
						0
					],
					[
						add(mul([omc, xfm.Z, xfm.X]), mul(s, xfm.Y)), 
						add(mul([omc, xfm.Z, xfm.Y]), mul(neg(s), xfm.X)), 
						add(mul([omc, xfm.Z, xfm.Z]), c), 
						0
					],
					[0, 0, 0, 1],
				]};
			}
		}
		
	}
	
	
	function is_num(xp) {
		return typeof(xp) == 'number';
	}
	function is_builtin(xp) {
		if(typeof(xp) != 'object') return false;
		if(xp.op == 'cos' || xp.op == 'sin' || xp.op == 'neg') return true;
		return false;
	}
	function is_const(xp) {
		return is_num(xp) 
			|| (is_builtin(xp) && is_const(xp.arg1)) 
			|| is_op(xp, 'uvar') // uncomment to distribute uvars
			|| is_op(xp, 'ovar'); // maybe not this one
	}
	function is_simple_term(xp) {
		if(is_num(xp) || (is_const(xp))) return true;
		if(xp.op == 'add') {
			if(!(is_num(xp.arg1[0]) || is_num(xp.arg1[1]))) return false;
			if(!(is_builtin(xp.arg1[0]) || is_builtin(xp.arg1[1]))) return false;
			return true;
		}
	}
	function is_matrix(xp) {
		return typeof(xp) == 'object' && xp.op == 'mat';
	}
	
	function multiply_matrices_and_vectors(op, a1, a2, xp) {
		if(op == 'mul') {
			if(is_matrix(a1[0]) && is_op(a1[1], 'vec')) {
				return matvec_mul(a1[0], a1[1]);
			}
			// BUG: probably a problem with mat*vec commutativity
			if(is_matrix(a1[1]) && is_op(a1[0], 'vec')) {
				return matvec_mul(a1[1], a1[0]);
			}
			
			if(is_matrix(a1[0]) && is_matrix(a1[1])) {
				return mat_mul(a1[0], a1[1]);
			}
		}
		
		return false;
	}
	
	function constant_fold(op, a1, a2, xp) {
		
		if(op == 'add') {
			// eliminate additions of length 1
			if(a1.length == 1) return a1[0];
			
			var m = false; // modified flag, for concatenated add-children
			var mc = 0; // counting combined constants
			var mz = 0; // counting removed zeros
			var cnst = 0;
			var o = [];
			
			for(var x of a1) {
				if(is_num(x)) {
					cnst += x;
					mc++;
					if(x == 0) mz++;
					continue;
				}
				
				if(is_op(x, 'add')) {
					o = o.concat(x.arg1);
					m = true;
					continue;
				}
				
				o.push(x);
			}
			
			m = m || mc > 1;
			
			if(o.length == 0) return cnst;
			
			if(!m && mz == 0 /* && !(mc > 0 && cnst == 0)*/) return false;
			
			
			if(cnst != 0) o.push(cnst);
			
			
			return {op: 'add', arg1: o};
		}
		
		if(op == 'mul') {
			
			
			// eliminate additions of length 1
			if(a1.length == 1) return a1[0];
			
			// collapse constants
			var m = false;
			var mc = 0;
			var cnst = 1;
			var o = [];
			var t_exist = [];
			var t_add = [];
			
			for(var x of a1) {
				if(x == 0) {
					return 0;
				}
				
				if(is_num(x)) {
					cnst *= x;
					mc++;
					continue;
				}
				
				if(is_op(x, 'mul')) {
					o = o.concat(x.arg1);
					m = true;
					continue;
				}
				

				if(is_op(x, 'term')) {
					t_exist.push(x);
					continue;
				}
				if(is_simple_term(x)) {
					t_add.push(x);
					continue;
				}
				
				o.push(x);
			}
			
			
			//construct a term from the parts
			var term = {op: 'term', arg1: 1, arg2: []}
			if(t_exist.length > 0) {
				for(var t of t_exist) {
					term.arg2 = term.arg2.concat(t.arg2);
					term.arg1 *= t.arg1;
				}
			}
			
			if(t_add.length > 0) {
				for(var t of t_add) {
					if(is_op(t, 'neg')) {
						term.arg1 *= -1;
						t = t.arg1;
					}
					term.arg2.push(t);
				}
			}
			
			if(term.arg2.length > 0) {
				term.arg1 *= cnst;
				cnst = 1;
				o.push(term);
			}
			else {
				cnst *= term.arg1;
			}
			
			
			m = m || mc > 1;
			
			if(o.length == 0) return cnst;
			if(!m && t_exist.length <= 1 && t_add.length == 0) return false;
			
			if(cnst != 1) o.push(cnst);
			return {op: 'mul', arg1: o};
		}
		
		if(op == 'term') {
			if(a1 == 0) return 0;
		}
		
		if(op == 'neg') {
			if(a1 == 0) return 0;
			if(is_num(a1)) {
				return -a1;
			}
		}
		
		if(op == 'cos') {
			if(a1 == 0) return 1;
			if(a1 == 'pi') return 0;
		}
		if(op == 'sin') {
			if(a1 == 'pi') return 1;
			if(a1 == 0) return 0;
		}
		
		return false;
	}
	
	function mat_mul(aa, bb) {
		var a = aa.arg1;
		var b = bb.arg1;
		var out = [[],[],[],[]];
		
		for(r = 0; r < 4; r++) {
			for(c = 0; c < 4; c++) {
				out[c][r] = add([
					mul(a[c][0], b[0][r]), 
					mul(a[c][1], b[1][r]),
					mul(a[c][2], b[2][r]),
					mul(a[c][3], b[3][r])
				]);
			}
		}
		
		return {op: 'mat', arg1: out};
	}
	
	function matvec_mul(mat, vec) {
		var v = vec.arg1;
		var m = mat.arg1;
		var out = [];
		
		for(r = 0; r < 4; r++) {
			out[r] = add([
				mul(v[r], m[0][r]), 
				mul(v[r], m[1][r]),
				mul(v[r], m[2][r]),
				mul(v[r], m[3][r])
			]);
		}
		
		return {op: 'vec', arg1: out};
	}
	
	function termKey(t) {
		if(!t.termKey) {
			t.termKey = t.arg2.slice()
				.map(function(xp) { return printXP(txtPrintFns, xp) })
				.sort()
				.join(':');
		}
		
		return t.termKey;
	}
	
	function terms_are_equal(a, b) {
		var aa = a.arg2.slice().map(function(xp) { return printXP(txtPrintFns, xp) }).sort().join(':');
		var bb = b.arg2.slice().map(function(xp) { return printXP(txtPrintFns, xp) }).sort().join(':');
		return aa == bb;
	}
	
	function combine_terms(op, a1, a2, xp) {
		if(op == 'add') {
			if(a1.length == 1) return a1[0];
			
			var out = [];
			var cache = {};
			
			// group all the terms by key
			for(var t of a1) {
				if(is_op(t, 'term')) {
					var k = termKey(t);
					cache[k] = cache[k] || [];
					cache[k].push(t);
				}
				else {
					out.push(t)
				}
			}
			
			var modified = false;
			
			for(var k in cache) {
				var list = cache[k];
				
				// push singular terms directly to output
				if(list.length == 1) {
					out.push(list[0]);
					continue;
				}
				
				modified = true;
				// combine common terms
				var sum = 0;
				for(var t of list) {
					sum += t.arg1;
				}
				
				out.push({
					op: 'term',
					arg1: sum,
					arg2: list[0].arg2,
				});
			}
			
			if(!modified) return false;
			
			if(out.length == 1) return out[0];
			
			return add(out);
		}
		
		return false;
	}
	
	// applies the distributive property of multiplication and addition widely
	function distribute_terms(op, a1, a2, xp) {
		if(op != 'mul') return false;
		if(a1.length == 1) return a1[0];
		
		var mult = a1.slice();
		var reject = [];
		
		var a = mult.pop();
		while(mult.length > 0) {
			var b = mult.pop();
			
			var o = simple_distribute(a, b);
			if(o === false) {
// 				console.log("failed to distribute: ", a, b );
				reject.push(a);
				a = b;
				continue;
			}
			
			a = o;
		}
		
		if(reject.length > 0) {
			reject.push(a);
			return {op: 'mul', arg1: reject};
		}
		
		return a;
		
		function simple_distribute(a1, a2) {
			var o = [];
			if(is_num(a1) && is_num(a2)) {
				return a1 * a2;
			} 
			if(is_op(a1, 'term') && is_num(a2)) {
				return {op: 'term', arg1: a1.arg1 * a2, arg2: a1.arg2};
			} 
			if(is_op(a2, 'term') && is_num(a1)) {
				return {op: 'term', arg1: a2.arg1 * a1, arg2: a2.arg2};
			} 
			
			if(is_op(a1, 'add') && is_op(a2, 'add')) {
				
				for(var i of a1.arg1) {
					for(var j of a2.arg1) {
						o.push(mul(i, j));
					}
				}
				return add(o);
			}
			
			if(is_op(a1, 'add') && (is_op(a2, 'term') || is_num(a2) || is_const(a2))) {
					
				for(var i of a1.arg1) {
					o.push(mul(i, a2));
				}
				return add(o);
			}
			
			if((is_op(a1, 'term') || is_num(a1) || is_const(a1)) && is_op(a2, 'add')) {
					
				for(var i of a2.arg1) {
					o.push(mul(i, a1));
				}
				return add(o);
			}
			
			return false;
		}
		
		return false;
	}
	
	function optimize_op(xp, fn) {
		if(typeof(xp) != 'object') {
			return [false, xp];
		}
		if(xp instanceof Array) {
			var m = false;
			var o = xp.map(function(x) { 
				var [m1, o1] = optimize_op(x, fn);
				m = m || m1;
				return o1;
			});
			return [m, o];
		}
		
		var modified = false;
		
		if(xp.op == 'mat') {
			var o = [];
			for(var a = 0; a < 4; a++) {
				o[a] = [];
				for(var b = 0; b < 4; b++) {
					var z = optimize_op(xp.arg1[a][b], fn);
					o[a][b] = z[1];
					
					modified = modified || z[0];
				}
			}
			return [modified, {op: 'mat', arg1: o}];
		}
		
		
		var [m1, a1] = optimize_op(xp.arg1, fn);
		var [m2, a2] = optimize_op(xp.arg2, fn);
		
		var out = fn(xp.op, a1, a2, xp);
		
		if(out === false) {
			return [m1 || m2, {op: xp.op, arg1: a1, arg2: a2}];
		}
		else return [true, out];
	}
	
	// breadth-first
	function bf_optimize_op(xp, fn) {
		if(typeof(xp) != 'object') {
			return [false, xp];
		}
		if(xp instanceof Array) {
			var m = false;
			var o = xp.map(function(x) { 
				
				var out = fn(xp.op, a1, a2, fn);
				if(out === false) {
					var [m1, o1] = bf_optimize_op(x, fn);
					m = m || m1;
				}
				else {
					m = true;
					o1 = out;
				}
				return o1;
			});
			return [m, o];
		}
		
		var modified = false;
		
		if(xp.op == 'mat') {
			var o = [];
			for(var a = 0; a < 4; a++) {
				o[a] = [];
				for(var b = 0; b < 4; b++) {
					var out = fn(xp, fn);
					
					if(out === false) {
						var z = bf_optimize_op(xp.arg1[a][b], fn);
						o[a][b] = z[1];
						
						modified = modified || z[0];
					}
					else {
						modified = true;
						o[a][b] = out;
					}
					
					
				}
			}
			return [modified, {op: 'mat', arg1: o}];
		}
		
		var out = fn(xp, fn);
		
		if(out === false) {
			var [m1, a1] = bf_optimize_op(xp.arg1, fn);
			var [m2, a2] = bf_optimize_op(xp.arg2, fn);
			
			return [m1 || m2, {op: xp.op, arg1: a1, arg2: a2}];
		}
		else return [true, out];
	}
	
	
	function walk_ops(xp, fn) {
		if(typeof(xp) != 'object') {
			return;
		}
		if(xp instanceof Array) {
			xp.map(function(x) { 
				walk_ops(x, fn);
			});
			return;
		}
		
		if(xp.op == 'mat') {
			for(var a = 0; a < 4; a++) {
				for(var b = 0; b < 4; b++) {
					walk_ops(xp.arg1[a][b], fn);
				}
			}
			return;
		}
		
		walk_ops(xp.arg1, fn);
		walk_ops(xp.arg2, fn);
		
		fn(xp);
	}
	
	
	
</script>

</head>
<body>
	
	<div class="controls">
		<select class="transform-type">
			<option value="">-- Select Transformation --</option>
			<option value="rotX">Rotation about X</option>
			<option value="rotY">Rotation about Y</option>
			<option value="rotZ">Rotation about Z</option>
			<option value="rotAxis">Rotation about Axis</option>
			<option value="translate">Translation</option>
			<option value="scale">Scale</option>
		</select>
		
		<div class="rotX-options transform-option" style="display:none;">
			<label>Theta</label><input type="edit" name="Theta" value="0"></input>
		</div>
		<div class="rotY-options transform-option" style="display:none;">
			<label>Theta</label><input type="edit" name="Theta" value="0"></input>
		</div>
		<div class="rotZ-options transform-option" style="display:none;">
			<label>Theta</label><input type="edit" name="Theta" value="0"></input>
		</div>
		
		<div class="rotAxis-options transform-option" style="display:none;">
			<label>Axis X</label><input type="edit" name="X" value="0"></input>
			<label>Axis Y</label><input type="edit" name="Y" value="0"></input>
			<label>Axis Z</label><input type="edit" name="Z" value="0"></input>
			<label>Theta</label><input type="edit" name="Theta" value="0"></input>
		</div>
		
		<div class="translate-options transform-option" style="display:none;">
			<label>X</label><input type="edit" name="X" value="0"></input>
			<label>Y</label><input type="edit" name="Y" value="0"></input>
			<label>Z</label><input type="edit" name="Z" value="0"></input>
		</div>
		
		<div class="scale-options transform-option" style="display:none;">
			<label>X</label><input type="edit" name="X" value="0"></input>
			<label>Y</label><input type="edit" name="Y" value="0"></input>
			<label>Z</label><input type="edit" name="Z" value="0"></input>
		</div>
		
		<button name="add">Add</button>
		
	</div>
	
	<div class="chain"></div>
	
	<div class="options">
		<div class="opt">
			<fieldset>
				<legend>Output style</legend>
				<div>
					<input name="matvec_output" type="radio" class="checkbox" value="matrix" />
					<span>Matrix</span>
				</div>
				
				<div>
					<input name="matvec_output" type="radio" class="checkbox" value="vector" checked/>
					<span>Vector</span>
				</div>
			</fieldset>
		</div>
		<div class="opt">
			<fieldset>
				<legend>Handedness</legend>
				<div>
					<input name="handedness" type="radio" class="checkbox" value="left" />
					<span>Left (DirectX)</span>
				</div>
				
				<div>
					<input name="handedness" type="radio" class="checkbox" value="right" checked/>
					<span>Right (OpenGL)</span>
				</div>
			</fieldset>
		</div>
		<div class="opt">
			<fieldset class="CAS-options">
				<legend>CAS Options</legend>
				<div>
					<input name="distribute" type="checkbox" class="checkbox" />
					<span>Distribute</span>
				</div>
				<div>
					<input name="factor_terms" type="checkbox" class="checkbox" checked />
					<span>Factor Terms</span>
				</div>
				<div>
					<input name="constant_fold" type="checkbox" class="checkbox" checked />
					<span>Fold Constants</span>
				</div>
				<div>
					<input name="factor_trig" type="checkbox" class="checkbox" checked />
					<span>Factor Trig Fns</span>
				</div>
			
			</fieldset>
		</div>
	</div>
	
	<div class="output">
		<button name="solve">Solve</button>
		<button name="clear">Clear</button>
		
		<div class="results"></div> 
		<div class="vars"></div> 
		<pre class="code"></pre> 
		
	</div>
	
</body>
</html>
